<?php

class BinarySearchTree extends BinaryTree 
{
	public function __construct(BinarySearchTreeNode $root)
	{
		$this->_root = $root;
	}
	
	public function add(BinarySearchTreeNode $node)
	{
		$this->_add($node, $this->_root);
	}
	
	protected function _add(BinarySearchTreeNode $insertNode, BinarySearchTreeNode $node)
	{
		if($node->compareTo($insertNode) < 0){
			if($node->getRight() == null){
				$node->setRight($insertNode);
				return true;
			}else{
				return $this->_add($insertNode, $node->getRight());
			}	
		}else{
			if($node->getLeft() == null){
				$node->setLeft($insertNode);
				return true;
			}else{
				return $this->_add($insertNode, $node->getLeft());
			}				
		}
	}
	
	public function get($value)
	{
		$node = $this->_search($value, $this->_root);
		if($node === false){
			return false;
		}else{
			return $node->getValue();
		}
	}
	
	public function remove($value)
	{
		$removeNode =& $this->_search($value, $this->_root);
		$removeCopy = clone($removeNode);
		$retNode = $removeNode;
		if($removeNode !== false){
			$this->_remove($removeNode);
			return $removeCopy->getValue();
		}else{
			return false;
		}
	}
	
	protected function _remove(BinarySearchTreeNode &$node)
	{
	    if ($node->getLeft() == null) { 
	        $node = $node->getRight();
	    } else if ($node->getRight() == null) {
	        $node = $node->getLeft();
	    } else {
	        
	        $temp =& $node->getLeft(); 

	        while ($temp->getRight() != null) {
	            $temp =& $temp->getRight();
	        }
	
	        $node->setValue($temp->getValue());
	        $node->setKey($temp->getKey());
	
	        $this->_remove($temp);	    	
	    }		
	}
	
	protected function &_search($value, BinarySearchTreeNode &$node = null)
	{
		if($node == null){
			return false;
		}else if($node->getValue() == $value){
			return $node;
		}else if($node->getValue() >= $value){
			return $this->_search($value, $node->getLeft());
		}else{
			return $this->_search($value, $node->getRight());
		}		
	}
}
?>